﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Xml;

using SimpleIR;
using System.Diagnostics.Contracts;

namespace PInfoModel
{
	/// <summary>
	/// This value type represents edges in the shape graph
	/// </summary>
	public struct PIMEdge : IEquatable<PIMEdge>
	{
		/// <summary>
		/// The offset of the edge in the memory structure that the pointers represented by this edge originate at.
		/// </summary>
		public readonly IRBasicAccessPath OffsetInSource;

		/// <summary>
		/// The offset in the memory structure that the pointers represented by this edge end at.
		/// </summary>
		public readonly IRBasicAccessPath OffsetInTarget;

		/// <summary>
		/// Indicate if this edge originates in a stack location.
		/// </summary>
		public readonly bool IsEvalStackSource;

		/// <summary>
		/// The int that is the id for the source (memory or stack location) of this edge.
		/// </summary>
		public readonly int SourceAddress;

		/// <summary>
		/// The int that is the id for the target of this edge.
		/// </summary>
		public readonly int TargetAddress;

		/// <summary>
		/// If the edge may represent references that are injective or if they may alias.
		/// </summary>
		public readonly bool IsInjective;

		/// <summary>
		/// If the edge represents pointers which are non-null.
		/// </summary>
		public readonly bool IsNonNull;

		/// <summary>
		/// A string with info about the traversal position of the edge.
		/// </summary>
		public readonly string CollectionTraverseInfo;

		/// <summary>
		/// General constuctor when you need to specify all the parameters.
		/// </summary>
		public PIMEdge(bool isstacksource, int sourceid, IRBasicAccessPath sourceaccep, int targetid, IRBasicAccessPath trgtaccep, bool inj, bool nonnull, string travinfo)
		{
			Contract.Requires(sourceaccep != null);
			Contract.Requires(trgtaccep != null);
			
			this.OffsetInSource = sourceaccep;
			this.OffsetInTarget = trgtaccep;
			this.IsEvalStackSource = isstacksource;
			this.SourceAddress = sourceid;
			this.TargetAddress = targetid;
			this.IsInjective = inj;
			this.IsNonNull = nonnull;
			this.CollectionTraverseInfo = travinfo;
		}

		public override string ToString()
		{
			string names;
			if((this.OffsetInSource.IsEmptyAccessPath) & (this.OffsetInTarget.IsEmptyAccessPath))
				names = "*";
			else if(this.OffsetInSource.IsEmptyAccessPath)
				names = "(*)." + this.OffsetInTarget.ToString();
			else if(this.OffsetInTarget.IsEmptyAccessPath)
				names = "(*" + this.OffsetInSource.ToString() + ")";
			else
				names = "(*" + this.OffsetInSource.ToString() + ")." + this.OffsetInTarget.ToString();

			return "(" + this.SourceAddress.ToString() + ", " + names + ",  -> " + (this.IsNonNull ? "" : "?") + this.TargetAddress.ToString() + " @ " + (this.IsInjective ? "inj " : "alias ") + this.CollectionTraverseInfo + ")";
		}

		internal void Serialize(PInfoSerializer sr)
		{
			sr.WriteStartTag("MEdge");

			sr.WriteBool("IsEval", this.IsEvalStackSource);

			sr.WriteInt("SAddr", this.SourceAddress);
			sr.WriteIRBasicAccessPath("SOff", this.OffsetInSource);

			sr.WriteInt("TAddr", this.TargetAddress);
			sr.WriteIRBasicAccessPath("TOff", this.OffsetInTarget);

			sr.WriteBool("IsInj", this.IsInjective);
			sr.WriteBool("IsNN", this.IsNonNull);
			sr.WriteString("CTI", this.CollectionTraverseInfo); 

			sr.WriteEndTag("MEdge");
		}

		internal static PIMEdge Deserialize(PInfoDeSerializer dsr)
		{
			dsr.ReadStartTag("MEdge");

			bool iseval = dsr.ReadBool("IsEval");

			int saddr = dsr.ReadInt("SAddr");
			IRBasicAccessPath soff = dsr.ReadIRBasicAccessPath("SOff");

			int taddr = dsr.ReadInt("TAddr");
			IRBasicAccessPath toff = dsr.ReadIRBasicAccessPath("TOff");

			bool isinj = dsr.ReadBool("IsInj");
			bool isnn = dsr.ReadBool("IsNN");
			string cti = dsr.ReadString("CTI");

			dsr.ReadEndTag("MEdge");

			return new PIMEdge(iseval, saddr, soff, taddr, toff, isinj, isnn, cti);
		}

		/// <summary>
		/// Compute the dgml representation for edges originating at a stack location.
		/// </summary>
		internal static void DGMLDumpStackRefEdges(PIMEdge[] es, string rootname, XmlWriter xmlw)
		{
			Dictionary<int, List<PIMEdge>> epd = DGMLPartitionEdgeTargets(es);

			foreach(KeyValuePair<int, List<PIMEdge>> ep in epd)
			{
				List<string> refnames = new List<string>();
				List<string> trgtnames = new List<string>();
				bool injv = true;
				bool nonnull = true;

				for(int i = 0; i < ep.Value.Count; ++i)
				{
					PIMEdge ee = ep.Value[i];
					refnames.Add(ee.OffsetInSource.NiceDisplayString());

					if((!ee.OffsetInTarget.IsEmptyAccessPath) && (!trgtnames.Contains(ee.OffsetInTarget.ToString())))
						trgtnames.Add(ee.OffsetInTarget.ToString());

					injv &= ee.IsInjective;
					nonnull &= ee.IsNonNull;
				}

				refnames.Sort();

				xmlw.WriteStartElement("Link");
				xmlw.WriteAttributeString("Id", rootname + "_" + ep.ToString());

				StringBuilder lsb = new StringBuilder();
				if(refnames.Count != 1)
					lsb.Append("{");

				for(int i = 0; i < refnames.Count; ++i)
				{
					String rrs = refnames[i];
					if(i != 0)
						lsb.Append(", ");
					lsb.Append(rrs);
				}

				if(refnames.Count != 1)
					lsb.Append("}");

				xmlw.WriteAttributeString("Label", lsb.ToString());

				StringBuilder tsb = new StringBuilder();
				trgtnames.Sort();
				tsb.Append("{");
				for(int i = 0; i < trgtnames.Count; ++i)
				{
					String rrs = trgtnames[i];
					if(i != 0)
						tsb.Append(", ");
					tsb.Append(rrs);
				}
				tsb.Append("}");
				
				xmlw.WriteAttributeString("TargetOffsets", tsb.ToString());

				xmlw.WriteAttributeString("Source", rootname);
				xmlw.WriteAttributeString("Target", ep.Key.ToString());
				
				xmlw.WriteAttributeString("TraverseInfo", (ep.Value.Count == 1 ? ep.Value[0].CollectionTraverseInfo : "Unknown"));
				xmlw.WriteAttributeString("MayAliasWMulti", (!injv || (ep.Value.Count != 1)).ToString());
				xmlw.WriteAttributeString("MayNull", (!nonnull).ToString());
				xmlw.WriteAttributeString("PureInjective", injv.ToString());

				xmlw.WriteEndElement();
			}
		}

		/// <summary>
		/// Compute the dgml representation for edges originating at a heap location.
		/// </summary>
		internal static void DGMLDumpHeapEdges(PIMEdge[] es, PIMNode sourcen, XmlWriter xmlw)
		{
			Dictionary<int, List<PIMEdge>> epd = DGMLPartitionEdgeTargets(es);

			foreach(KeyValuePair<int, List<PIMEdge>> ep in epd)
			{
				List<string> refnames = new List<string>();
				List<string> trgtnames = new List<string>();
				bool injv = true;
				bool nonnull = true;

				for(int i = 0; i < ep.Value.Count; ++i)
				{
					PIMEdge ee = ep.Value[i];
					refnames.Add(ee.OffsetInSource.NiceDisplayString());

					if((!ee.OffsetInTarget.IsEmptyAccessPath) && (!trgtnames.Contains(ee.OffsetInTarget.ToString())))
						trgtnames.Add(ee.OffsetInTarget.ToString());

					injv &= ee.IsInjective;
					nonnull &= ee.IsNonNull;
				}

				refnames.Sort();

				xmlw.WriteStartElement("Link");
				xmlw.WriteAttributeString("Id", sourcen.LocationAddress + "_" + ep.Key);

				StringBuilder lsb = new StringBuilder();
				if(refnames.Count != 1)
					lsb.Append("{");

				for(int i = 0; i < refnames.Count; ++i)
				{
					String rrs = refnames[i];
					if(i != 0)
						lsb.Append(", ");
					lsb.Append(rrs);
				}

				if(refnames.Count != 1)
					lsb.Append("}");

				xmlw.WriteAttributeString("Label", lsb.ToString());

				trgtnames.Sort();
				StringBuilder tsb = new StringBuilder();
				if(trgtnames.Count != 0)
				{
					for(int i = 0; i < trgtnames.Count; ++i)
					{
						String rrs = trgtnames[i];
						if(i != 0)
							tsb.Append(" ");
						tsb.Append(rrs);
					}
				}

				xmlw.WriteAttributeString("TargetOffsets", tsb.ToString());

				xmlw.WriteAttributeString("Source", sourcen.LocationAddress.ToString());
				xmlw.WriteAttributeString("Target", ep.Key.ToString());

				xmlw.WriteAttributeString("TraverseInfo", (ep.Value.Count == 1 ? ep.Value[0].CollectionTraverseInfo : "Unknown"));
				xmlw.WriteAttributeString("MayAliasWMulti", (!injv || (ep.Value.Count != 1)).ToString());
				xmlw.WriteAttributeString("PureInjective", injv.ToString());
				xmlw.WriteAttributeString("MayNull", (!nonnull).ToString());
				
				xmlw.WriteEndElement();
			}
		}

		/// <summary>
		/// Partition the edges into equivalence classes for handling multi edges.
		/// </summary>
		private static Dictionary<int, List<PIMEdge>> DGMLPartitionEdgeTargets(PIMEdge[] es)
		{
			Dictionary<int, List<PIMEdge>> epd = new Dictionary<int, List<PIMEdge>>();

			foreach(PIMEdge ee in es)
			{
				if(!epd.ContainsKey(ee.TargetAddress))
					epd.Add(ee.TargetAddress, new List<PIMEdge>());
				epd[ee.TargetAddress].Add(ee);
			}

			return epd;
		}

		public static bool operator ==(PIMEdge e1, PIMEdge e2)
		{ return e1.Equals(e2); }

		public static bool operator !=(PIMEdge e1, PIMEdge e2)
		{ return !e1.Equals(e2); }

		public override int GetHashCode()
		{ return this.SourceAddress ^ this.OffsetInSource.GetHashCode() ^ this.TargetAddress ^ this.OffsetInTarget.GetHashCode(); }

		public override bool Equals(object obj)
		{ return (obj is PIMEdge) && this.Equals((PIMEdge)obj); }

		public bool Equals(PIMEdge other)
		{
			if(this.OffsetInSource != other.OffsetInSource || this.OffsetInTarget != other.OffsetInTarget)
				return false;

			if(this.IsEvalStackSource != other.IsEvalStackSource)
				return false;

			if(this.SourceAddress != other.SourceAddress || this.TargetAddress != other.TargetAddress)
				return false;

			if(this.IsInjective != other.IsInjective || this.IsNonNull != other.IsNonNull)
				return false;

			if(!this.CollectionTraverseInfo.Equals(other.CollectionTraverseInfo))
				return false;

			return true;
		}
	}
}
